package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class BinaryWatch {

	public static void main(String[] args) {
		BinaryWatch object = new BinaryWatch();
		object.readBinaryWatch(4);
	}
	
	List<String> res = new ArrayList<>();
	List<Integer> list = new ArrayList<>();
	List<Integer> exceed = new ArrayList<>();
	
	public List<String> readBinaryWatch(int num) {
		if(num > 9){
			return res;
		}
		if(num == 0){
			res.add("0:00");
			return res;
		}
		for (int i = 0; i < 6; i++) {
			exceed.add(1 << i);
		}
		res.clear();
		list.clear();
		int[] nums = {1, 2, 4, 8, 16, 32, 1 * 60, 2 * 60, 4 * 60, 8 * 60};
		backtrack(nums, 10, num, 0);
		Collections.sort(res, new Comparator<String>() {
			@Override
			public int compare(String time1, String time2) {
				int hour1 = Integer.valueOf(time1.substring(0, time1.indexOf(':')));
				int hour2 = Integer.valueOf(time2.substring(0, time2.indexOf(':')));
				int minute1 = Integer.valueOf(time1.substring(time1.indexOf(':') + 1, time1.length()));
				int minute2 = Integer.valueOf(time2.substring(time2.indexOf(':') + 1, time2.length()));
				if(hour1 == hour2){
					return minute1 - minute2;
				}else{
					return hour1 - hour2;
				}
			}
		});
		System.out.println(res);
		return res;
	}
	
	public void backtrack(int[] nums, int n, int k, int start){
		if(k < 0){
			return;
		}
		if (k == 0) {
			//getTime
			getTime();
		} else {
			int i;
			for (i = start; i < n; i++) {
				list.add(nums[i]);
				backtrack(nums, n, k - 1, i + 1);  //寻找下一个
				list.remove(list.size() - 1);
			}
		}
	}
	
	public void getTime(){
		int minuteSum = 0;
		int size = list.size();
		int hourSum = 0;
		for (int i = 0; i < size; i++) {
			if(list.get(i) < 60){
				minuteSum += list.get(i);
			}else{
				hourSum += list.get(i);
			}
		}
		//判断非法的亮灯情况
		if(hourSum >= 12 * 60 || minuteSum >= 60){
			return;
		}
		hourSum = hourSum + minuteSum;
		int hour = hourSum / 60;
		int minute = hourSum % 60;
		if(hour >= 12){
			return;
		}
		String time = hour + ":" + (minute < 10 ? "0" + minute : minute);
		res.add(time);
	}
}
